package 栈;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Test {
    /**
     * 出栈入栈匹配
     */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        //定义一个栈
        Stack<Integer> stack=new Stack<>();
        int p1=0;
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j<popA.length&&!stack.isEmpty()&&stack.peek().equals(popA[j])) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    public boolean IsPopOrder1(int [] pushA,int [] popA) {
        //定义一个栈
        Stack<Integer> stack=new Stack<>();
        int p1=0;
        int p2=0;
        while (p2!=popA.length) {
          if(!stack.isEmpty()&&stack.peek().equals(popA[p2])) {
              p2++;
              stack.pop();
          }else {
              if(p1==popA.length) {
                  return false;
              }
              stack.push(pushA[p1++]);
          }
        }
        return true;
    }
    /**
     *
     * 括号匹配问题
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(c=='{'||c=='['||c=='(') {
                stack.push(c);
            }else {
                //如果为空就返回false
                if(stack.isEmpty()) {
                    return false;
                }
                char str=stack.peek();
                if(str=='['&&c==']'||str=='('&&c==')'||str=='{'&&c=='}') {
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        return true;
    }
    /**
     * 逆波兰表达式求值
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            //数字进栈
            String str=tokens[i];
            if(str.equals("+")||str.equals("-")||str.equals("/")||str.equals("*")) {
                int a2=stack.pop();
                int a1=stack.pop();
                switch (str) {
                case "+":
                    stack.add(a1+a2);
                break;
                case "-":
                    stack.add(a1-a2);
                break;
                case "*":
                    stack.add(a1*a2);
                    break;
                case "/":
                    stack.add(a1/a2);
                    break;
            }
            }else {
                //字符串转数字
                stack.add(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}
class MinStack {
    /**
     * 最小栈
     */
    //定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void push(int val) {
        if(stack2.isEmpty()) {
            stack2.push(val);
        }else {
            stack1.push(val);
            if(stack2.peek()>val) {
                stack2.push(val);
            }
        }
    }
    public void pop() {
        if(stack1.pop().equals(stack2.peek())) {
            stack2.pop();
        }
    }

    public int top() {
        return stack1.peek();
    }

    public int getMin() {
    return  stack2.peek();
    }
}
class MyCircularQueue {
    int []array;
    boolean p;
    //p为真就是满
    //否则就是不满
    int front;
    int rear;
    public MyCircularQueue(int k) {
        array=new int[k];
    }

    public boolean enQueue(int value) {
        //插入一个元素
        //判满
        if(isFull()) {
            return false;
        }
        array[rear]=value;
        rear=(rear+1+array.length)%array.length;
        return true;
    }

    //删除一个元素
    public boolean deQueue() {
        //判空
        if(isEmpty()) {
            return false;
        }
        front=(front+1+array.length)%array.length;
        return true;
    }

    public int Front() {
        return array[front];
    }

    public int Rear() {
        int n=array.length;
        return array[(rear-1+n)%n];
    }

    public boolean isEmpty() {
    //判空
        return rear==front;
    }

    public boolean isFull() {
        //判满
        return (rear+1+array.length)%array.length==front;
    }
}
class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.empty()&&stack2.empty();
    }
}
class MyStack {
    //队列实现栈
    Queue<Integer> queue1;

    public MyStack() {
        queue1=new LinkedList<>();
    }
    public void push(int x) {
     queue1.offer(x);
    }
    public int pop() {
        int size=queue1.size();
        while (size!=1) {
            size--;
            queue1.offer(queue1.poll());
        }
        return queue1.poll();
    }

    public int top() {
        int size=queue1.size();
        while (size!=1) {
            size--;
            queue1.offer(queue1.poll());
        }
      int  n=queue1.poll();
        queue1.offer(n);
        return n;
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}